IMSH: An Iterative Heuristic for SRLG Diverse Routing in WDM Mesh Networks

摘要

Survivable routing of a connection involves computation of a pair of diverse routes such that at most one mute fails when failures occur in the network topology. A subset of links in the network that share the risk of failure at the same time are said to belong to a Shared Risk Link Group (SRLG) [3]. A network with shared risk link groups defined over its links is an SRLG network. A failure of an SRLG is equivalent to the failure of all the links in the SRLG. For a connection to he survivable in an SRLG network its working and protection paths must he routed on SRLG diverse paths. SRLG diverse routing problem has been proved to he NP-complete in [1]. According to the quality of service requirement of a survivable connection request, dedicated protection or shared protection can be used to establish the connection request. With dedicated protection, the connection is established on both the SRLG diverse working and protection paths. The simplest heuristic for computing SRLG diverse path pair is the two-step approach, hut it suffers from the trap topology problem. In [Z] an iterative heuristic (ITSH) using the two-step approach was proposed to compute least cost SRLG diverse path pair. Suurballe’s algorithm computes a pair of least cost link-disjoint paths between a node pair. In this work we present a modified Suurballe’s heuristic for computing the SRLG diverse routes between a node pair. We then propose an iterative heuristic (IMSH) which uses the modified Suurballe’s heuristic for computing the least cost SRLG diverse routes. We also present an 1/2-cost-improvement optimality check criterion for dedicated protection.